package com.example;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author loubobooo
 * @Description #60. 排列序列
 * @Date 2022/2/22
 */
public class PermutationSequence {

    private List<String> list = new ArrayList<>();

    /**
     * 方法描述:给出集合[1,2,3,...,n]，其所有元素共有n! 种排列
     * 按大小顺序列出所有排列情况，并一一标记，当n = 3 时, 所有排列如下：
     * "123"
     * "132"
     * "213"
     * "231"
     * "312"
     * "321"
     * 给定n 和k，返回第k个排列。
     * <p>
     * 示例 1：
     * <p>
     * 输入：n = 3, k = 3
     * 输出："213"
     *
     * @param: [n, k]
     * @return: java.lang.String
     * @author: loubobooo
     * @date: 2022/2/22
     */
    public String getPermutation(int n, int k) {
        // 逆康托展开
        // 一开始已经提过了，康托展开是一个全排列到一个自然数的双射，因此是可逆的。即对于上述例子，在（1，2，3，4，5）给出61可以算出起排列组合为 34152。由上述的计算过程可以容易的逆推回来，具体过程如下：
        //
        //用 61 / 4! = 2余13，说明a[5]=2,说明比首位小的数有2个，所以首位为3。
        //用 13 / 3! = 2余1，说明a[4]=2，说明在第二位之后小于第二位的数有2个，所以第二位为4。
        //用 1 / 2! = 0余1，说明a[3]=0，说明在第三位之后没有小于第三位的数，所以第三位为1。
        //用 1 / 1! = 1余0，说明a[2]=1，说明在第二位之后小于第四位的数有1个，所以第四位为5。
        //最后一位自然就是剩下的数2啦。
        //通过以上分析，所求排列组合为 34152。
        int[] factor = new int[]{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        List<Integer> digit = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            digit.add(i);
        }
        k--;// 先-1才是康托展开的值
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = n; i >= 1; i--) {
            int r = k / factor[i - 1];
            k = k % factor[i - 1];
            stringBuilder.append(digit.get(r+1));// 剩余数里r+1个数为当前位
            digit.remove(r+1);
        }
        return stringBuilder.toString();
    }

    private void backTracking(int start, int n, StringBuilder stringBuilder) {
        // 设置终止条件
        if (start == n) {
            // 添加结果
            list.add(stringBuilder.toString());
            return;
        }
        // startIndex记录一个起始位置
        // for循环相当于横向遍历
        for (int i = 1; i <= n; i++) {
            if (!stringBuilder.toString().contains(String.valueOf(i))) {
                //添加节点
                stringBuilder.append(i);
                // 回溯，相当于纵向遍历
                backTracking(start + 1, n, stringBuilder);
                // 回撤节点
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        PermutationSequence permutationSequence = new PermutationSequence();
        String permutation = permutationSequence.getPermutation(3, 3);
    }

}
